\documentclass[12pt]{article}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{times}
\usepackage{verbatim}

\newtheorem{defn}{Definition}
\newtheorem{lem}{Lemma}
\newtheorem{thm}{Theorem}

\begin{document}
\section*{Task Descriptor}
\paragraph{}
A task descriptor has:
\begin{itemize}
\item \verb=id=: globally unique ID
\item \verb=sp=: stack pointer
\item \verb=ret=: return value
\item \verb=parent=: ID of parent task
\item \verb=state=: either Active, Ready, or Defunct
\item some pointers
\end{itemize}
\paragraph{}
Active tasks are either executing, entering the kernel, or exiting the
kernel. There is exactly one active task at any given time. Ready tasks are in
a state where they can become the active task; when a Ready task reaches the
head of the ready queue, it becomes Active. Defunct tasks have called
\verb=Exit()=, but have not been cleaned up.
\paragraph{}
Later on, we will have special Blocked states (e.g. waiting on I/O). You do
not need to implement this part for Assignment 1.

\section*{Task Creation}
\paragraph{}
To create a task, we need to:
\begin{itemize}
\item get an unused TD
\item assign some memory
\end{itemize}
\paragraph{}
However, we don't have the luxury of memory management; therefore, we need
to pre-allocate a task descriptor table of fixed size. The memory region
\verb=0x00218000 - 0x01fffffc= is available. RedBoot resides below
\verb=0x00218000=; it also maintains a stack in the area of \verb=0x01fffffc=,
as can be verified via hexdump inspection. (All bits are set in empty memory.)
For the kernel, you can simply provide a preset amount of low memory for the
image and a preset amount of high memory for the kernel stack.
\paragraph{}
Initially, the task return value is uninitialized and the task state is Ready;
the parent ID can be retrieved from the currently active task (the one that
called \verb=Create()=).

\section*{Scheduling}
\paragraph{}
Most consumer operating systems use time-sharing scheduling; in these systems,
no task is permitted to run for too long. However, this imposes high overhead
for context switching - since there are no guarantees that a context switch
will happen at an opportune time, every context switch must save and restore
everything. For this reason, time-sharing is rare in real-time operating
systems; instead, tasks are allowed to voluntarily relinquish the processor.
As a safeguard, such systems often keep a watchdog timer. Each task resets this
timer upon activation; if the timer reaches, say, 10 seconds, the system
initiates a reboot.
\paragraph{}
In our operating system, we have the \verb=Pass()= system call; this causes
the calling task to yield the processor. The main problem, then, is one of
priority - how do we determine who goes next? An optimal schedule would activate
the task that most needs to run. This is NP-complete, so we settle for a crude
heuristic: we maintain multiple priority queues and always pick the
highest-priority Ready task.
\paragraph{}
From this perspective, all system calls imply a manipulation of the priority
queue. As such, both insertion into and deletion from the queue must be
constant-time; circular linked lists are often used for this purpose. One
way to maintain these is to have list pointers directly in the task
descriptors; however, you are free to implement this as you like.
\end{document}
